Many current large-scale multiagent team implementations can be characterizedas following the belief-desire-intention (BDI) paradigm, with explicitrepresentation of team plans. Despite their promise, current BDI teamapproaches lack tools for quantitative performance analysis under uncertainty.Distributed partially observable Markov decision problems (POMDPs) are wellsuited for such analysis, but the complexity of finding optimal policies insuch models is highly intractable. The key contribution of this article is ahybrid BDI-POMDP approach, where BDI team plans are exploited to improve POMDPtractability and POMDP analysis improves BDI team plan performance. Concretely,we focus on role allocation, a fundamental problem in BDI teams: which agentsto allocate to the different roles in the team. The article provides three keycontributions. First, we describe a role allocation technique that takes intoaccount future uncertainties in the domain; prior work in multiagent roleallocation has failed to address such uncertainties. To that end, we introduceRMTDP (Role-based Markov Team Decision Problem), a new distributed POMDP modelfor analysis of role allocations. Our technique gains in tractability bysignificantly curtailing RMTDP policy search; in particular, BDI team plansprovide incomplete RMTDP policies, and the RMTDP policy search fills the gapsin such incomplete policies by searching for the best role allocation. Oursecond key contribution is a novel decomposition technique to further improveRMTDP policy search efficiency. Even though limited to searching roleallocations, there are still combinatorially many role allocations, andevaluating each in RMTDP to identify the best is extremely difficult. Ourdecomposition technique exploits the structure in the BDI team plans tosignificantly prune the search space of role allocations. Our third keycontribution is a significantly faster policy evaluation algorithm suited forour BDI-POMDP hybrid approach. Finally, we also present experimental resultsfrom two domains: mission rehearsal simulation and RoboCupRescue disasterrescue simulation.
展开▼
